#include <unordered_map>
#include <unordered_set>
#include <iostream>

using namespace std;


//BFS解决拓扑问题3：火星词典（解法优化）
class Solution3 {
    bool check=true;
public:
    string alienOrder(vector<string>& words) 
    {
        string ret;int count=0;
        int m=words.size();
        //vector<vector<int>> edges(m);
        unordered_map<char,unordered_set<char>> edges;
        unordered_map<char,int> in;
        for(int i=0;i<m;i++)
            for(int j=0;j<words[i].size();j++)  in[words[i][j]]=0;
        for(int i=0;i<words.size()-1;i++)
        {
            //for(int j=i+1;j<words.size();j++)
            //{
                if(!DicComp(words[i],words[i+1],edges,in)) check=false;
            //}
        }
        if(!check) return{};//整个word只要有一种非法情况。
        //if(count==0)    return {};
        queue<char> q;
        for(auto it:in)
        {
            //cout<<it.first<<":"<<in[it.first]<<" ";
            if(in[it.first]==0)
            {
                q.push(it.first);
            }
        }
        //if(q.size()==in.size()) return{};
        while(!q.empty())
        {
            auto top=q.front();q.pop();
            //cout<<top<<" ";
            ret+=top;
            for(auto it:edges[top])
            {
                in[it]--;
                if(in[it]==0)   q.push(it);
            }
        }
        for(auto it:in)
        {
            if(it.second>0)    return {};
        }
        return ret;
    }
    bool DicComp(string& prev,string& next,unordered_map<char,unordered_set<char>> &edges,unordered_map<char,int>& in)
    {
        int minsize=min(prev.size(),next.size());
        //循环内结束说明比较出了有效字典序，返回true
        for(int i=0;i<minsize;i++)
        {
            if(prev[i]!=next[i])
            {
                if(!edges[prev[i]].count(next[i]))//当一个被插入的元素首次进入某个拓扑序列时，in才会更新
                    in[next[i]]++;
                edges[prev[i]].insert(next[i]);                    
                //cout<<in[next[i]]<<" ";
                return true;
            }
        }
        //循环内没有结束说明前面min个字符相等,如果前面的字符串比后面的小，说明合法返回true;
        if(prev.size()<next.size()) return true;
        //如果前后两个字符串完全相等，说明合法返回true;
        if(prev==next)  return true;
        //没有任何一种合法情况，返回false;
        return false;
    }
};



int main()
{

    return 0;
}